package first.codeTop.tencent;

/**
 * @ClassName LC92
 * @description:
 * @author: 荣燊
 * @create: 2021-10-25 14:18
 **/
public class LC92 {
    // 反转链表 II
    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        ListNode node1 = new ListNode(-1);
        node1.next = node;
        reverseListNode3(node);
        while (node1 != null) {
            System.out.println(node1.val);
            node1 = node1.next;
        }
    }

    // 反转指定位置的链表
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }
        ListNode dumpyNode = new ListNode(-1);
        dumpyNode.next = head;
        ListNode pre = dumpyNode;
        // 1.left节点的前一个节点
        for (int i=0; i<left-1; i++) {
            pre = pre.next;
        }
        // 2.从pre再到 right节点
        ListNode rightNode = pre;
        for (int i=0; i<right-left+1; i++) {
            rightNode = rightNode.next;
        }
        // 切断出一个子链表
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;
        // 开始切
        pre.next = null;
        rightNode.next = null;
        // 4.反转链表
        reverseListNode3(leftNode);
        // 5.回到原来链表，接上
        pre.next = rightNode;
        leftNode.next = curr;
        return dumpyNode.next;
    }

    // 反转链表，使用递归
    public static ListNode reverseListNode1(ListNode head) {
        if (head.next == null || head == null) {
            return head;
        }
        ListNode node = reverseListNode2(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

    // 反转链表，不使用递归,while循环
    public static ListNode reverseListNode2(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void reverseListNode3(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}
